/**
 * @author Sebastian
 * @version 2.0
 * @date 2024/7/11 20:53
 */
// 回文链表
    // https://leetcode.cn/problems/palindrome-linked-list/
public class Solution234 {
    // 先找到中间节点，然后反转后半个链表
    public boolean isPalindrome(ListNode head) {
        ListNode slow = head;
        ListNode fast = head;
        // 快慢指针找到中间节点
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        // 处理奇数节点情况
        if (fast != null) slow = slow.next;
        // 反转之后链表
        slow = reverse(slow);
        fast = head;
        while (slow != null) {
            if (slow.val != fast.val) {
                return false;
            }
            slow = slow.next;
            fast = fast.next;
        }
        return true;
    }

    // 反转链表
    private ListNode reverse(ListNode node) {
        ListNode pre = null;
        while (node != null) {
            ListNode tmp = node.next;
            node.next = pre;
            // 更新当前指针和前驱指针
            pre = node;
            node = tmp;
        }
        return pre;
    }
}
